Answer: 78. Each multiple of 5 gives a zero (there are enough even numbers available). Multiples of 25 have two 5 factors, and those of 125 have 3. So total 64 for multiples of 5, another 12 for those that are multiples of 25 as well, and another 2 for multiples of 125.
Note: The symbol "." is used as a multiplication sign below
Principal 1: If the thing we are counting is an outcome of a multistage process, then the number of outcomes is the product of the number of choices for each stage
Principal 2: If the thing we are counting can happen in different exclusive ways, then the number of outcomes is the sum of the number of outcomes through each way
Principal 3: Counting the complement requires subtraction
Principal 4: n distinct items can be arranged in n! ways
(BerkeleyMC Chap 2 - Prob 8) In how many ways can 10 men and 10 women be paired off
Answer: 10!
Instructor Notes: Its important for kids to understand that it only involves arranging 10 items and not 20. Draw an analogy with just arranging 10 people in a line. Work with smaller numbers as required.
(BerkeleyMC Chap 2 - Prob 9) What if they were not getting married but just making best friends?
Answer: 19.17.15....1
Instructor Notes: Start with smaller numbers. Make sure kids understand how duplicates are being taken care of (for example, always start choosing for remaining people in alphabetic order)
MCDiaries - Page 124, Prob 4: Prince Ivan is on a quest to free Princess Masha, who has been imprisoned in the castle. The castle door has a simple digital lock with ten buttons, numbered 0 to 9. The door is guarded by a hungry dragon, Pashka, who likes hot dogs. The door lock can be opened by typing a secret 4-digit code, and Pashka can be distracted by hot dogs. It takes 1 second for Prince to try out a single 4-digit combination, and it takes 20 seconds for Pashka to gulp down a single hot dog. After Ivan opens the lock, it will take him one minute to fetch Masha and fly off on his magic carpet.
How many hot dogs should Ivan pack to safely rescue Princess Masha? (Answer: 503)
Suppose that Ivan knows in advance that the secret code is composed of odd digits - how many hotdogs? (Answer: 35)
Suppose that Ivan knows that secret code is composed of odd digits and has exactly one digit 5 in it - how many hotdogs? (Answer: 16)
Suppose that Ivan knows that secret code is composed of odd digits and has at least one digit 5 in it - how many hotdogs? (Answer: 22)
http://www.geometer.org/mathcircles/combprobs.pdf - 26 (sum of possibilities) - A man has 10 friends. He has a party everyday and doesn't want to invite exactly the same group again. How many parties can he have. (2^10-1)
(MC Chap 11 - Prob 60) A rook stands on the leftmost box of a 1x30 strip of squares and can shift right by any number of squares in any move (Kids can start with smaller size strip to start)
In how many ways can the rook get to rightmost square (2^28)
In how many ways can the rook get to the rightmost square in 7 steps (28C6)
Homework Problem
MartinShCol - 1.14 (colored bowling pins, do with checkers) - there are bowling pins of red color and black color. Can you select 10 pins from these and place them in position of bowling pins, so that no equilateral triangle has all vertices of the same color?
References:
Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg
Mathematical Circle Diaries, Year 1, by Anna Burago
A Decade of the Berkeley Math Circle. The American Experience, Volume 1. Zvezdelina Stankova, Tom Rike